package lc.q201_250;

import lc.ListNode;

import java.util.Stack;

/**
 * 反转一个单链表。
 *
 * @author lgb
 * @date 2020/08/23
 **/
public class Q206 {

    public ListNode reverseList(ListNode head) {
        Stack<Integer> nums = new Stack<>();
        while (head != null) {
            nums.push(head.val);
            head = head.next;
        }
        ListNode watch = new ListNode(-1);//
        ListNode next = watch;
        while (!nums.isEmpty()) {
            next.next = new ListNode(nums.pop());
            next = next.next;
        }
        return watch.next;
    }

    public ListNode reverseList2(ListNode head) {// 递归方式，需要返回尾节点
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode next = head.next;
        head.next = null;
        ListNode listNode = reverseList2(next);
        listNode.next = head;
        return listNode;
    }

}
